package chapter04_RecursionAndDynamic;

/**
 * 描述：
 *      数字转换为字母的可能性
 *      给定-一个字符串str, str 全部由数字字符组成，如果str中某一个或某相邻两个字符组
 * 成的子串值在1~26 之间，则这个子串可以转换为一个字母。规定"1"转换为"A"，"2"转换为"B"，"3"转换为"C..."26"转换为"Z"。
 * 写一个函数，求str 有多少种不同的转换结果，并返回种数。
 *      '0'不能转换为任何字母
 * @author hl
 * @date 2021/7/11 9:30
 */
public class ConvertNum {

    public static void main(String[] args) {
        String str = "11111";
        ConvertNum convertNum = new ConvertNum();
        int count = convertNum.num1(str);
        int count2 = convertNum.num2(str);
        System.out.println(count);
        System.out.println(count2);
    }

    public int num1(String str){
        return process(str, 0);
    }

    private int process(String str, int index) {
        if (index >= str.length()) {
            return 1;
        }
        char cur = str.charAt(index);
        if (cur > '0' && cur <= '9') {
            int res = process(str, index + 1);
            if (index + 1 < str.length() && (cur - '0') * 10 + (str.charAt(index + 1) - '0') < 27) {
                res += process(str, index + 2);
            }
            return res;
        }
        return 0;
    }

    public int num2(String str){
        int dp = str.charAt(str.length() - 1) > '0' &&  str.charAt(str.length() - 1) < '9' ? 1 : 0;
        int dpNext = 1;
        int temp = 0;
        char cur;
        for (int i = str.length() - 2; i >= 0; i--) {
            cur = str.charAt(i);
            temp = dp;
            if (cur > '0' && cur < '9') {
                if ((cur - '0') * 10 + str.charAt(i + 1) - '0' < 27) {
                    dp += dpNext;
                }
            }else{
                dp = 0;
            }
            dpNext = temp;
        }
        return dp;
    }

}
